package class03;

import utils.ArrayUtil;


/**
 * 无序数组 相邻的数不相等 找局部最小值
 */
public class Code04_局部最小值 {
    public static void main(String[] args) {
        int times = 10;
        for (int i = 0; i < times; i++) {
            int[] arr = ArrayUtil.generateRandomArrayNoEqual(100, 100);
            //int[] arr = new int[]{82, 73, 66, 17, 74, 72, 60, 49, 76, 3, 84, 59, 99, 6, 2, 98};
            int index = findMinIndex(arr);
            if (!check(arr, index)) {
                System.out.println("fuck error");
                ArrayUtil.printArray(arr);
                System.out.println("index:" + index);
            }
        }
        System.out.println("over");
    }

    /**
     * 无序数组 相邻的数不相等 找局部最小值
     */
    private static int findMinIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }

        int N = arr.length - 1;
        if (N == 1) {
            return 0;
        }

        if (arr[0] < arr[1]) {
            return 0;
        }

        if (arr[N - 1] > arr[N]) {
            return N;
        }

        int L = 0;
        int R = N - 1;
        while (L < R - 1) {
            int mid = (L + R) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }
        }
        return arr[L] < arr[R] ? L : R;

    }

    /**
     * 数组中局部最小值的校验方法
     */
    public static boolean check(int[] arr, int minIndex) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int leftIndex = minIndex - 1;
        int rightIndex = minIndex + 1;

        if (minIndex == 0) {
            return arr[minIndex + 1] > arr[minIndex];
        }

        //左边数组越界直接返回true 只看右边就行
        boolean leftOK = leftIndex > 0 ? arr[leftIndex] > arr[minIndex] : true;
        boolean rightOK = rightIndex < arr.length ? arr[rightIndex] > arr[minIndex] : true;
        return leftOK && rightOK;
    }
}
